package org.czl.leetcode4;

public class l3290 {
    public static void main(String[] args) {
        //[3,2,5,6]  [2,-6,4,-5,-3,2,-7]
        System.out.println(maxScore(new int[]{3, 2, 5, 6}, new int[]{2, -6, 4, -5, -3, 2, -7}));
    }
    //在以i为结尾 选j个数的最高乘法得分
    public static long maxScore(int[] a, int[] b){
        int n = b.length;
        long[][] dp = new long[n + 1][5];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < 5; j++){
                dp[i][j] = Long.MIN_VALUE / 2;
            }
        }
        for(int i = 1; i < n; i++){
            for(int j = 1; j < 5; j++){
                dp[i][j] = dp[i - 1][j - 1] + a[j - 1] * b[i - 1];
                dp[i][j] = Math.max(dp[i][j - 1], dp[i][j]);
            }
        }
        return dp[n][4];
    }
}
